package work.lianbiao;

import work.ListNode;

public class Problem19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {


        ListNode ans = new ListNode(0, head);
        ListNode listNode = ans;
        int count = 1;

        while (head.next != null) {
            count = count + 1;
            head = head.next;
        }
        int length = count - n;
        for (int i = 1; i <= length; i++) {
            ans = ans.next;
        }
        ans.next = ans.next.next;

        ListNode wdh = listNode.next;

        return listNode;
    }

//可用双指针解决

    //解决这种问题的时候，return head 他永远指向第一个节点，
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        ListNode first = new ListNode(0, head);
        ListNode dummy = first;
        ListNode second = head;
        for (int i = 0; i < n; i++) {
            second = second.next;
        }
        while (second != null) {
            first = first.next;
            second = second.next;
        }
        first.next = first.next.next;

        return dummy.next;

    }


    public static void main(String[] args) {
        int[] a = {1};
        ListNode node = ListNode.listNodeFromArray(a);
        Problem19 problem19 = new Problem19();
        problem19.removeNthFromEnd1(node, 1);

    }

    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode ans = new ListNode(0, head);
        ListNode slow = ans, fast = ans;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return ans.next;
    }


}
